import java.util.*;

public class Leetcode {
}

//leetcode:207:课程表
class Solution1 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //创建一个数组存储每个点对应的入度
        int[] in = new int[numCourses];
        //创建哈希表存储入度为0的点，和它出度所指向的所有点形成的链表
        Map<Integer, List<Integer>> edges = new HashMap<>();

        //建图
        for(int i = 0; i < prerequisites.length; i++){
            int a = prerequisites[i][0], b = prerequisites[i][1];
            if(!edges.containsKey(b)){
                edges.put(b,new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++;
        }

        //拓扑排序
        //(1)将入度为0的点放入队列中
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0){
                q.add(i);
            }
        }

        //(2)bfs
        //进行入度为0的点，的出度所指向的点的入度删除
        while(!q.isEmpty()){
            int t = q.poll();
            //得到入度为0的点后边链表的所有值，如果此时得到的值为最后一个点（入度为0，出度为0）就创建一个空表
            for(int a : edges.getOrDefault(t,new ArrayList<>())){
                //进行对应点入度的删除
                in[a]--;
                //如果此时的点的入度为0，就放入队列中
                if(in[a] == 0){
                    q.add(a);
                }
            }
        }

        //4.判断是否成环
        //如果成环就必然，点的入度不为0
        for(int i = 0; i < numCourses; i++){
            if(in[i] != 0) return false;
        }
        return true;
    }
}

//leetcode:210:课程表II
class Solution2 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //创建一个数组存储每个点对应的入度
        int[] in = new int[numCourses];
        //创建一个链表
        List<List<Integer>> edges = new ArrayList<>();
        //每一层进行初始化
        for(int i = 0; i < numCourses; i++){
            edges.add(new ArrayList<>());
        }

        //建图
        for(int i = 0; i <prerequisites.length; i++){
            int a = prerequisites[i][0], b = prerequisites[i][1];
            edges.get(b).add(a);
            //增加a这个点的入度
            in[a]++;
        }

        //拓扑排序
        //(1)将入度为0的点放入队列中
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses;i++){
            if(in[i] == 0){
                q.add(i);
            }
        }

        //(2)bfs
        int[] ret = new int[numCourses];
        int index = 0;
        while(!q.isEmpty()){
            int t = q.poll();
            ret[index++] = t;
            for(int a : edges.get(t)){
                in[a]--;
                if(in[a] == 0) q.add(a);
            }
        }

        //判断
        if(index == numCourses) return ret;
        else return new int[0];
    }
}